package leetcodev1.字符串;

import leetcodev1.链表.Solution;

public class LeetCode43 {
    //字符串相乘
    //123*89
    public String multiply(String num1, String num2) {
        StringBuilder reverseRet = new StringBuilder();
        int length1 = num1.length(), length2 = num2.length(), index1 = length1 - 1, index2 = length2 - 1, next = 0;
        while (index1 >= 0 || index2 >= 0) {
            char a = index1 >= 0 ? num1.charAt(index1) : '1';
            char b = index2 >= 0 ? num2.charAt(index2) : '1';
            int num = (a - '0') * (b - '0') + next;
            reverseRet.append(num % 10);
            next = num / 10;
            index1--;
            index2--;
        }
        if (next != 0) {
            reverseRet.append(next);
        }
        return reverseRet.reverse().toString();
    }
}

class Answer {
    //利用加法
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        String ans = "0";
        int m = num1.length(), n = num2.length();
        //用num2的每一位 与num1的每一位做乘法
        for (int i = n - 1; i >= 0; i--) {
            StringBuffer curr = new StringBuffer();
            int add = 0;
            for (int j = n - 1; j > i; j--) {
                curr.append(0);//移位 补0
            }
            int y = num2.charAt(i) - '0';
            //每一位相乘
            for (int j = m - 1; j >= 0; j--) {
                int x = num1.charAt(j) - '0';
                int product = x * y + add;
                curr.append(product % 10);
                add = product / 10;//进位
            }
            if (add != 0) {
                curr.append(add % 10);
            }
            //字符串相加
            ans = addStrings(ans, curr.reverse().toString());
        }
        return ans;
    }

    //字符串相加
    public String addStrings(String num1, String num2) {
        int i = num1.length() - 1, j = num2.length() - 1, add = 0;
        StringBuffer ans = new StringBuffer();
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            int result = x + y + add;
            ans.append(result % 10);
            add = result / 10;
            i--;
            j--;
        }
        ans.reverse();
        return ans.toString();
    }

    //相乘后位数 [m+n-1,m+n]
    public String multiply1(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        int m = num1.length(), n = num2.length();
        int[] ansArr = new int[m + n];//99*99最多4位 10*10=100最小3位
        //num1的每一位与num2每一位相乘
        for (int i = m - 1; i >= 0; i--) {
            int x = num1.charAt(i) - '0';
            for (int j = n - 1; j >= 0; j--) {
                int y = num2.charAt(j) - '0';
                ansArr[i + j + 1] += x * y;//>这个值会>10//越小的数约后面
            }
        }
        //从小到大
        for (int i = m + n - 1; i > 0; i--) {
            ansArr[i - 1] += ansArr[i] / 10;//处理数据进位
            ansArr[i] %= 10;//剩余的数
        }
        int index = ansArr[0] == 0 ? 1 : 0;
        StringBuffer ans = new StringBuffer();
        while (index < m + n) {
            ans.append(ansArr[index]);
            index++;
        }
        return ans.toString();
    }

}
